#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"sparse.h"

// -从文件读取数据
Node * List_read(char * filename){

    // -only read
    FILE * fptr = fopen(filename,"r");
    if(NULL == fptr){

        printf("open file %s failed.\n",filename);
        return NULL;
    }
    int index = 0;
    int value = 0;
    Node * head = NULL;
    while(fscanf(fptr,"%d %d ",&index,&value) == 2){

        head = List_insert(head,index,value);
    }
    fclose(fptr);
    return head;
}

static Node * List_insert(Node * head,int index,int value){
    if(0 == value){

        return head;
    }
    if(NULL == head){

        return Node_create(index,value);
    }
    // -插入到head前面
    if(head->index > index){

        Node * ptr = Node_create(index,value);
        ptr->next = head;
        return ptr;
    }
    // -相等则不需要增加新的节点
    if(head->index == index){

        head->value += value;
        // -等于0 则删除节点
        if(0 == head->value){

            Node * ptr = head;
            // -head->next可能为NULL
            head = head->next;
            free(ptr);
        }
        // -这个head也可能为NULL 
        return head;
    }
    // -递归（在链表长度短的情况比较好）
    head->next = List_insert(head->next,index,value);
}

static Node * Node_create(int index,int value){

    Node * node = malloc(sizeof(Node));
    if(NULL == node){
        printf("malloc sizeof(Node) failed.\n");
        return NULL;
    }
    node->index = index;
    node->value = value;
    return node;
}

Node * List_copy(Node * arr){

    // -must init
    Node * distArray = NULL;
    while(NULL!=arr){

        distArray = List_insert(distArray,arr->index,arr->value);
        arr = arr->next;
    }
    return distArray;
}

// -将数据存储到文件里面
int List_save(char * filename,Node * arr){

    FILE * fptr = fopen(filename,"w");
    if(NULL == fptr){

        printf("open file %s failed.\n",filename);
        return -1;
    }
    while(NULL != arr){

        fprintf(fptr,"%d %d\n",arr->index,arr->value);
        arr = arr->next;
    }   
    fclose(fptr);
    return 0;
}
// -合并两个链表
Node * List_merge(Node * arr1,Node * arr2){

    // -deep copy
    Node * arr3 = List_copy(arr1);
    while(NULL!=arr2){

        arr3 = List_insert(arr3,arr2->index,arr2->value);
        arr2 = arr2->next;
    }
    return arr3;
}
// -释放内存
void List_destory(Node * arr){

    Node * ptr = NULL;
    while(NULL!=arr){

        ptr = arr;
        arr = arr->next;
        free(arr);
    }
}

int main(int argc,char * argv[]){



    return EXIT_SUCCESS;
}


////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////反转链表///////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

Node * List_reverse(Node * head){

    if(NULL == head){

        return NULL;
    }
    if(NULL == head->next){

        return head;
    }
    // -revHead指向反转的头节点
    Node * revHead = NULL;
    // -orignHead指向未翻转的头节点
    Node * orignHead = head;
    // -origSecon指向未翻转的第二个节点
    Node * origSecon = NULL;

    while(orignHead){

        origSecon = orignHead->next;
        orignHead->next = revHead;
        revHead = orignHead;
        orignHead = origSecon;
    }
    Node * ptr = revHead;
    while(ptr){

        printf("%d ",ptr->value);
        ptr = ptr->next;
    }
    return revHead;
}
